package coin.yang;

import java.util.Objects;

public class LinkEx {
    public static void main(String[] args) {

        LinkList<String> list = new LinkList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        list.add("f");
        list.add("g");
        LinkList<String> list2 = new LinkList<>();
        list2.add("a");
        list2.add("b");
        list2.add("c");
        list2.add("d");
        list2.add("e");
        list2.add("f");
        list2.add("g");
        // list.add(3, "h");
        // list.remove(3);
        // System.out.println(list.indexOf("e"));
        // System.out.println(list.subList(2, 6));
        System.out.println(list.equals(list2));
        System.out.println(list);

    }

}

// 实现LinkedList
class LinkList<E> {

    private Node<E> first; // 头节点
    private Node<E> last; // 尾节点
    private int size = 0; // 节点个数/元素个数

    // 添加元素
    public void add(E e) {
        // 构建新节点
        Node<E> node = new Node<>(null, e, null);
        // 判断是否是第一个元素
        if (size == 0) {
            // 如果是第一个节点，那么新节点就是头节点
            this.first = node;
        } else {
            // 原来的尾节点的下一位是现在的新节点
            this.last.next = node;
            // 新节点的上一位是原来的尾节点
            node.prev = this.last;
        }
        // 新节点现在应该是最后一个节点
        this.last = node;
        // 元素个数+1
        size++;
    }

    // 插入元素
    public void add(int index, E e) {
        // 判断下标是否越界
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        // 构建新节点
        Node<E> node = new Node<>(null, e, null);
        // 判断是否插入在尾部
        if (index == size) {
            add(e);
        } else if (index == 0) { // 插在头部
            // 新节点的下一位是原来头节点
            node.next = this.first;
            // 头节点的上一位是现在的新节点
            this.first.prev = node;
            // 现在的新节点才是头节点
            this.first = node;
            // 元素个数+1
            size++;
        } else { // 插在中间
            // 获取要插入的下标位置上对应的节点
            Node<E> n = this.getNode(index);
            // 原来节点的上一位的下一个指向是现在的新节点
            n.prev.next = node;
            // 新节点的上一位是原来节点的上一位
            node.prev = n.prev;
            // 新节点的下一位是原来的节点
            node.next = n;
            // 原来节点的上一位是现在的新节点
            n.prev = node;
            // 元素个数+1
            size++;
        }
    }

    // 移除元素
    public void remove(int index) {
        // 判断下标是否越界
        this.outOfBounds(index);
        // 判断节点位置
        if (size == 1) { // 判断是否只有1个节点
            this.first = this.last = null;
        } else if (index == 0) { // 移除头节点
            // 现在的头节点应该挪到原来的第二位
            this.first = this.first.next;
            // 去掉原来头节点的下一位指向
            this.first.prev.next = null;
            // 现在头节点的上一位应该清空
            this.first.prev = null;
        } else if (index == size - 1) { // 移除尾节点
            // 现在的为尾节点应该是原来的倒数第二位
            this.last = this.last.prev;
            // 原来尾节点的上一位应该清空
            this.last.next.prev = null;
            // 现在尾节点的下一位应该清空
            this.last.next = null;
        } else { // 移除其他位置上的节点
            // 先获取这个节点
            Node<E> node = this.getNode(index);
            // 当前节点的上一位指向当前节点的下一位
            node.prev.next = node.next;
            // 当前节点的下一位指向当前节点的上一位
            node.next.prev = node.prev;
            // 清空当前节点的上一位指向
            node.prev = null;
            // 清空当前节点的下一位指向
            node.next = null;
        }
        // 元素个数-1
        size--;
    }

    // 获取元素第一次出现的下标位置
    public int indexOf(E e) {
        // 获取头节点
        Node<E> n = this.first;
        for (int i = 0; i < size; i++) {
            if (Objects.equals(n.item, e))
                return i;
            // 后挪一位
            n = n.next;
        }
        // 如果整个循环结束，都没有返回，那么说明没有这个元素
        return -1;
    }

    // 移除指定的元素
    public void remove(E e) {
        // 获取下标
        int index = this.indexOf(e);
        if (index != -1) remove(index);
    }

    // 判断是否越界
    private void outOfBounds(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    // 找到指定下标对应的节点
    private Node<E> getNode(int index) {
        Node<E> n;
        if (index <= size / 2) {
            // 如果要找的元素在前半边，从前往后找
            int i = 0;
            n = this.first;
            while (i < index) {
                // 后推一位
                n = n.next;
                // 下标+1
                i++;
            }
        } else {
            // 如果要找的元素在后半边，从后往前找
            int i = size - 1;
            n = this.last;
            while (i > index) {
                // 前推一位
                n = n.prev;
                // 下标-1
                i--;
            }
        }
        return n;
    }

    // 获取元素个数
    public int size() {
        return size;
    }

    // 判断列表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 判断集合中是否包含指定的元素
    public boolean contains(E e) {
        return indexOf(e) != -1;
    }

    // 清空列表
    public void clear() {
        // 获取头节点
        Node<E> n = this.first;
        for (int i = 0; i < size - 1; i++) {
            // 挪到下一位上
            n = n.next;
            // 将上一个节点的下一位指向清除
            n.prev.next = null;
            // 将当前节点的上一位指向清理掉
            n.prev = null;
        }
        // 将头尾清空
        this.first = this.last = null;
        // 节点个数重置为0
        size = 0;
    }

    // 获取指定下标位置上的元素
    public E get(int index) {
        // 判断下标是否越界
        this.outOfBounds(index);
        // 获取这个下标对应的节点
        return this.getNode(index).item;
    }

    // 替换指定下标位置上的元素
    public void set(int index, E e) {
        // 判断下标是否越界
        this.outOfBounds(index);
        // 获取这个下标对应的节点进行元素替换
        this.getNode(index).item = e;
    }

    // 获取指定元素最后一次出现的下标
    public int lastIndexOf(E e) {
        // 获取尾节点
        Node<E> n = this.last;
        for (int i = size - 1; i > 0; i--) {
            // 判断元素是否相等
            if (Objects.equals(n.item, e)) return i;
            n = n.prev;
        }
        // 如果循环结束都没有返回，说明没有这个元素
        return -1;
    }

    // 截取子列表
    public LinkList<E> subList(int fromIndex, int toIndex) {
        // 判断下标是否合法
        if (toIndex > size || fromIndex < 0 || fromIndex > toIndex)
            throw new IllegalArgumentException("下标参数不正确！！！");
        // 构建新的子列表
        LinkList<E> sub = new LinkList<>();
        // 获取原列表中起始下标对应的节点
        Node<E> n = this.getNode(fromIndex);
        for (int i = 0; i < toIndex - fromIndex; i++) {
            // 获取元素放入子列表
            sub.add(n.item);
            // 后推一位
            n = n.next;
        }
        return sub;
    }

    // 判断两个列表是否相等
    public boolean equals(Object o) {
        // 判断地址是否相等
        if (this == o) return true;
        // 判断参数是否为空
        if (o == null) return false;
        // 判断类型是否一样
        if (this.getClass() != o.getClass()) return false;
        // 转换
        LinkList<E> list = (LinkList<E>) o;
        // 判断元素个数是否一样
        if (this.size != list.size) return false;
        // 判断列表中的元素是否相同
        Node<E> n1 = this.first;
        Node<E> n2 = list.first;
        for (int i = 0; i < size; i++) {
            if (!Objects.equals(n1.item, n2.item)) return false;
        }
        // 整个循环结束，都没有返回，那么说明所有的元素都一样
        return true;
    }

    // 转化为字符串
    @Override
    public String toString() {
        // 判断集合中是否有元素
        if (size == 0) return "[]";
        // 遍历元素
        StringBuilder sb = new StringBuilder("[");
        Node<E> n = this.first;
        for (int i = 0; i < size; i++) {
            // 拼接元素
            sb.append(n.item).append(", ");
            // 后挪
            n = n.next;
        }
        String str = sb.toString();
        // 截取
        str = str.substring(0, str.length() - 2);
        return str += "]";
    }

    // 定义内部类表示节点
    private static class Node<E> {

        private Node<E> prev; // 上一个节点
        private E item; // 存储的元素
        private Node<E> next; // 下一个节点

        public Node(Node<E> prev, E item, Node<E> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }

    }
}
